package leetcode_day._2021._202109._0110;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/9/5 14:56
 * 用 Rand7() 实现 Rand10()
 * 算法：数学   拒绝采样
 * rand10 返回 1 ~ 10 的概率是相同的，即 1 ~ 10 出现的概率相同
 * rand7() 表示随机返回 [1, 7] 区间内的数
 * ----------------------------------------------
 * 由 rand2() 实现 rand4()
 * rand2() + rand2()
 * 1 1 2, 1 2 3, 2 1 3, 2 2 4
 * 这样 p(2) = 1/4, p(3) = 1/2, p(4) = 1/4，概率不同
 * (rand2() - 1) * 2 + rand2()
 * 0 1 1, 0 2 2, 2 1 3, 2 2 4
 * 这样概率就相同了
 * ----------------------------------------------
 * 由 rand4() 实现 rand2()
 * rand4() % 2 + 1
 * 1 1 2, 0 1 1, 1 1 2, 0 1 1
 * randX 实现 randY
 * X < Y, (randX - 1) * Y + randY, 实现的区间 [1, X * Y]
 * X > Y, X 是 Y 的倍数, randX % Y + 1 = randY
 */
public class _05_470 {

    public int rand10() {
        while (true) {
            int num = (rand7() - 1) * 7 + rand7();
            if (num <= 40) return num % 10 + 1;
        }
    }

    public int rand7() {
        return 1;
    }

}
